package practise.alogrithm.hundredInterviewQuestions.secondTime;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * Created by Richard on 7/26/2014.
 */
public class CheckArrayFromStack {
    /**
     * the popOrder should be in a reverse order, replay the procedure, always remove the element from push list,
     * if it is not right, then put it to a temp stack, this stack equal to pop in advance
     * @param pushOrder
     * @param popOrder
     * @return
     */
    public boolean verify(List<Integer> pushOrder, List<Integer> popOrder){
        Stack<Integer> temp = new Stack<>();
        while(!pushOrder.isEmpty()){
            if(pushOrder.get(0).equals(popOrder.get(popOrder.size() - 1))){
                pushOrder.remove(0);
                popOrder.remove(popOrder.size()-1);
            }
            else{
                temp.add(pushOrder.remove(0));
            }
            while(!temp.isEmpty()&&temp.peek().equals(popOrder.get(popOrder.size()-1))){
                temp.pop();
                popOrder.remove(popOrder.size()-1);
            }
        }

        return temp.isEmpty()&&popOrder.isEmpty();

    }

    public static void main(String[] args){
        CheckArrayFromStack checkArrayFromStack = new CheckArrayFromStack();
        System.out.println("result:"+checkArrayFromStack.verify(new ArrayList<Integer>(Arrays.asList(new Integer[]{1,2,3,4,5})),new ArrayList<Integer>(Arrays.asList(new Integer[]{4,5,3,2,1}))));
        System.out.println("result:"+checkArrayFromStack.verify(new ArrayList<Integer>(Arrays.asList(new Integer[]{1,2,3,4,5})),new ArrayList<Integer>(Arrays.asList(new Integer[]{4,3,5,1,2}))));
    }
}
